.Dd $Mdocdate: February 23 2015 $
.Dt BN_MOD_MUL_MONTGOMERY 3
.Os
.Sh NAME
.Nm BN_mod_mul_montgomery ,
.Nm BN_MONT_CTX_new ,
.Nm BN_MONT_CTX_init ,
.Nm BN_MONT_CTX_free ,
.Nm BN_MONT_CTX_set ,
.Nm BN_MONT_CTX_copy ,
.Nm BN_from_montgomery ,
.Nm BN_to_montgomery
.Nd Montgomery multiplication
.Sh SYNOPSIS
.In openssl/bn.h
.Ft BN_MONT_CTX *
.Fo BN_MONT_CTX_new
.Fa void
.Fc
.Ft void
.Fo BN_MONT_CTX_init
.Fa "BN_MONT_CTX *ctx"
.Fc
.Ft void
.Fo BN_MONT_CTX_free
.Fa "BN_MONT_CTX *mont"
.Fc
.Ft int
.Fo BN_MONT_CTX_set
.Fa "BN_MONT_CTX *mont"
.Fa "const BIGNUM *m"
.Fa "BN_CTX *ctx"
.Fc
.Ft BN_MONT_CTX *
.Fo BN_MONT_CTX_copy
.Fa "BN_MONT_CTX *to"
.Fa "BN_MONT_CTX *from"
.Fc
.Ft int
.Fo BN_mod_mul_montgomery
.Fa "BIGNUM *r"
.Fa "BIGNUM *a"
.Fa "BIGNUM *b"
.Fa "BN_MONT_CTX *mont"
.Fa "BN_CTX *ctx"
.Fc
.Ft int
.Fo BN_from_montgomery
.Fa "BIGNUM *r"
.Fa "BIGNUM *a"
.Fa "BN_MONT_CTX *mont"
.Fa "BN_CTX *ctx"
.Fc
.Ft int
.Fo BN_to_montgomery
.Fa "BIGNUM *r"
.Fa "BIGNUM *a"
.Fa "BN_MONT_CTX *mont"
.Fa "BN_CTX *ctx"
.Fc
.Sh DESCRIPTION
These functions implement Montgomery multiplication.
They are used automatically when
.Xr BN_mod_exp 3
is called with suitable input, but they may be useful when several
operations are to be performed using the same modulus.
.Pp
.Fn BN_MONT_CTX_new
allocates and initializes a
.Vt BN_MONT_CTX
structure.
.Fn BN_MONT_CTX_init
initializes an existing uninitialized
.Vt BN_MONT_CTX .
.Pp
.Fn BN_MONT_CTX_set
sets up the
.Fa mont
structure from the modulus
.Fa m
by precomputing its inverse and a value R.
.Pp
.Fn BN_MONT_CTX_copy
copies the
.Vt BN_MONT_CTX
.Fa from
to
.Fa to .
.Pp
.Fn BN_MONT_CTX_free
frees the components of the
.Vt BN_MONT_CTX ,
and, if it was created by
.Fn BN_MONT_CTX_new ,
also the structure itself.
.Pp
.Fn BN_mod_mul_montgomery
computes
.Pp
.D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1
.Pp
and places the result in
.Fa r .
.Pp
.Fn BN_from_montgomery
performs the Montgomery reduction
.Pp
.D1 Fa r No = Fa a No * R^-1.
.Pp
.Fn BN_to_montgomery
computes
.Pp
.D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R .
.Pp
Note that
.Fa a
must be non-negative and smaller than the modulus.
.Pp
For all functions,
.Fa ctx
is a previously allocated
.Vt BN_CTX
used for temporary variables.
.Pp
The
.Vt BN_MONT_CTX
structure is defined as follows:
.Bd -literal
typedef struct bn_mont_ctx_st {
	int ri;		/* number of bits in R */
	BIGNUM RR;	/* R^2 (used to convert to Montgomery form) */
	BIGNUM N;	/* The modulus */
	BIGNUM Ni;	/* R*(1/R mod N) - N*Ni = 1
			 * (Ni is only stored for bignum algorithm) */
	BN_ULONG n0;	/* least significant word of Ni */
	int flags;
} BN_MONT_CTX;
.Ed
.Pp
.Fn BN_to_montgomery
is a macro.
.Pp
.Sy Warning:
The inputs must be reduced modulo
.Fa m ,
otherwise the result will be outside the expected range.
.Sh RETURN VALUES
.Fn BN_MONT_CTX_new
returns the newly allocated
.Vt BN_MONT_CTX ,
and
.Dv NULL
on error.
.Pp
.Fn BN_MONT_CTX_init
and
.Fn BN_MONT_CTX_free
return no values.
.Pp
For the other functions, 1 is returned for success, 0 on error.
The error codes can be obtained by
.Xr ERR_get_error 3 .
.Sh SEE ALSO
.Xr bn 3 ,
.Xr BN_add 3 ,
.Xr BN_CTX_new 3 ,
.Xr ERR_get_error 3
.Sh HISTORY
.Fn BN_MONT_CTX_new ,
.Fn BN_MONT_CTX_free ,
.Fn BN_MONT_CTX_set ,
.Fn BN_mod_mul_montgomery ,
.Fn BN_from_montgomery
and
.Fn BN_to_montgomery
are available in all versions of SSLeay and OpenSSL.
.Pp
.Fn BN_MONT_CTX_init
and
.Fn BN_MONT_CTX_copy
were added in SSLeay 0.9.1b.
